// https://leetcode.cn/problems/minimum-falling-path-sum/

// 算法思路总结：
// 1. 使用原地动态规划，直接在原矩阵上修改
// 2. 每个位置累加上一行的最小相邻值
// 3. 最后取最后一行最小值作为结果
// 4. 时间复杂度：O(n²)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        int n = matrix.size();

        for (int i = 1 ; i < n ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                int minVal = matrix[i - 1][j];
                if (j > 0) minVal = std::min(minVal, matrix[i - 1][j - 1]);
                if (j < n - 1) minVal = std::min(minVal, matrix[i - 1][j + 1]);
                matrix[i][j] += minVal;
            }
        }

        return *min_element(matrix[n - 1].begin(), matrix[n - 1].end());
    }
};

int main()
{
    vector<vector<int>> vv1 = {{2,1,3}, {6,5,4}, {7,8,9}};
    vector<vector<int>> vv2 = {{-19,57}, {-40,-5}};

    Solution sol;

    cout << sol.minFallingPathSum(vv1) << endl;
    cout << sol.minFallingPathSum(vv2) << endl;

    return 0;
}